//
// Created by ade on 2022/8/15.
//
#include <iostream>
#include <vector>
#include <deque>

using namespace std;

struct Node {
    int val;
    Node *prev;
    Node *next;

    Node() : val(0), prev(nullptr), next(nullptr) {}

    Node(int val) : val(val), prev(nullptr), next(nullptr) {}

    Node(int val, Node *prev) : val(val), prev(prev), next(nullptr) {}

    Node(int val, Node *prev, Node *next) : val(val), prev(prev), next(next) {}
};

class MyCircularDeque {
public:
    int k = 0;
    int count = 0;

    Node * dummyHead = nullptr;
    Node * dummyEnd = nullptr;

    MyCircularDeque(int k) {
        this->k = k;
        dummyHead = new Node(-1);
        dummyEnd = new Node(-1);
        dummyHead->next = dummyEnd;
        dummyEnd->prev = dummyHead;
    }

    bool insertFront(int value) {
//        cout << "count:" << count << endl;
        if (count >= k) return false;

        Node * next = dummyHead->next;
        Node * newNode = new Node(value);
        newNode->next = next;
        newNode->prev = dummyHead;
        dummyHead->next = newNode;
        next->prev = newNode;

        count++;
        return true;
    }

    bool insertLast(int value) {
        if (count >= k) return false;

        Node * prev = dummyEnd->prev;
        Node * newNode = new Node(value);
        prev->next = newNode;
        newNode->prev = prev;
        newNode->next = dummyEnd;
        dummyEnd->prev = newNode;

        count++;
        return true;
    }

    bool deleteFront() {
        if (count == 0) return false;

        Node * next = dummyHead->next;
        next->next->prev = dummyHead;
        dummyHead->next = next->next;
        delete next;

        count--;
        return true;
    }

    bool deleteLast() {
        if (count == 0) return false;

        Node * prev = dummyEnd->prev;
        prev->prev->next = dummyEnd;
        dummyEnd->prev = prev->prev;
        delete prev;

        count--;
        return true;
    }

    int getFront() {
        return dummyHead->next->val;
    }

    int getRear() {
        return dummyEnd->prev->val;
    }

    bool isEmpty() {
        return count == 0;
    }

    bool isFull() {
        return count == k;
    }
};

int main() {
    // ["MyCircularDeque","insertLast","insertLast","insertFront","insertFront","getRear","isFull","deleteLast","insertFront","getFront"]
    // [[3],[1],[2],[3],[4],[],[],[],[4],[]]
    MyCircularDeque d(3);
    cout << d.insertLast(1) << endl;
    cout << d.insertLast(2) << endl;
    cout << d.insertFront(3) << endl;
    cout << d.insertFront(4) << endl;
    cout << d.isFull() << endl;
    cout << d.deleteLast() << endl;
    cout << d.insertFront(4) << endl;
    cout << d.getFront() << endl;

    return 0;
}